Lý thuyết độ phức tạp tính toán (tiếng Anh: computational complexity theory) là một nhánh của lý thuyết tính toán trong lý thuyết khoa học máy tính và toán học tập trung vào phân loại các vấn đề tính toán theo độ khó nội tại của chúng. Ở đây, một vấn đề tính toán được hiểu là một vấn đề có thể giải được bằng máy tính (nói chung có nghĩa là vấn đề có thể được diễn đạt dưới dạng toán học). Một vấn đề tính toán có thể hiểu là một tập các trường hợp và lời giải cho các trường hợp đó. Ví dụ như kiểm tra tính nguyên tố là vấn đề xác định xem một số cho trước có phải số nguyên tố hay không. Mỗi trường hợp của vấn đề là một số tự nhiên, và lời giải cho mỗi trường hợp là có hoặc không tùy theo số đó có là nguyên tố hay không.Một vấn đề được coi là khó nếu lời giải của nó đòi hỏi nhiều tài nguyên, bất kể sử dụng thuật toán nào. Lý thuyết độ phức tạp tính toán chuyển ý tưởng trực quan này thành mệnh đề toán học chặt chẽ, bằng cách đưa ra các mô hình tính toán để nghiên cứu các vấn đề này và tính lượng tài nguyên cần thiết để giải quyết chúng, chẳng hạn như thời gian hay bộ nhớ. Ngoài ra còn có những tài nguyên khác cũng được sử dụng, chẳng hạn như lượng thông tin liên lạc (dùng trong độ phức tạp truyền thông), số lượng cổng logic trong mạch (dùng trong độ phức tạp mạch) và số lượng bộ xử lý (dùng trong tính toán song song). Một trong những nhiệm vụ của lý thuyết độ phức tạp tính toán là xác định các giới hạn của những gì máy tính có thể làm và không thể làm.Hai ngành khác trong lý thuyết khoa học máy tính có liên hệ chặt chẽ với độ phức tạp tính toán là phân tích thuật toán và lý thuyết khả tính. Điểm khác biệt mấu chốt giữa phân tích thuật toán và lý thuyết độ phức tạp tính toán là ngành thứ nhất tập trung vào phân tích lượng tài nguyên cần thiết cho một thuật toán nhất định, trong khi ngành thứ hai nghiên cứu các câu hỏi về tất cả các thuật toán có thể dùng để giải quyết vấn đề. Cụ thể hơn, nó tìm cách phân loại các vấn đề theo lượng tài nguyên cần thiết để giải quyết chúng. Việc giới hạn lượng tài nguyên là điểm khác biệt giữa độ phức tạp tính toán và lý thuyết khả tính: lý thuyết khả tính nghiên cứu xem những vấn đề nào có thể giải được về mặt nguyên tắc, mà không giới hạn tài nguyên.